package demo10;


import sun.misc.OSEnvironment;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {

//    //1.树左下角的值(bfs)
//    public int findBottomLeftValue(TreeNode root) {
//        // bfs
//        int ret = 0;
//        Queue<TreeNode> queue = new LinkedList<>();
//        queue.offer(root);
//        while(!queue.isEmpty()) {
//            //队首元素即为所求
//            TreeNode node = queue.peek();
//            if(node.left == null && node.right == null) {
//                ret = node.val;
//            }
//            int size = queue.size();
//            while(size > 0) {
//                TreeNode cur = queue.poll();
//                if(cur.left != null) {
//                    queue.offer(cur.left);
//                }
//                if(cur.right != null) {
//                    queue.offer(cur.right);
//                }
//                size--;
//            }
//        }
//        return ret;
//    }

//    //1.找树左下角的值(dfs)
//    private int maxDepth = -1;
//    private int result = 0;
//    public int findBottomLeftValue(TreeNode root) {
//        dfs(root, 0);
//        return result;
//    }

//    public int cur;
//    public TreeNode curBuildTree(int[] inorder, int[] postorder, int start, int end) {
//        if(start > end) {
//            return null;
//        }
//        //根节点
//        TreeNode root = new TreeNode(postorder[cur]);
//        //找中序遍历中根节点下标
//        int indexRoot = fundRoot(inorder, start, end ,postorder[cur]);
//        cur--;
//        root.left = curBuildTree(inorder, postorder, start, indexRoot - 1);
//        root.right = curBuildTree(inorder, postorder, indexRoot + 1, end);
//        return root;
//    }
//
//    public int fundRoot(int[] inorder, int start, int end ,int key) {
//        for(int i = start; i <= end; i++) {
//            if(inorder[i] == key) {
//                return i;
//            }
//        }
//        return 0;
//    }
//    2.构建二叉树(后续)
//    public TreeNode buildTree(int[] inorder, int[] postorder) {
//        this.cur = postorder.length - 1;
//        return curBuildTree(inorder, postorder, 0, inorder.length - 1);
//    }


    //创建二叉树(2)
    private int cur;
    private TreeNode createTree(int[] preorder, int[] inorder, int start, int end) {
        if(start > end) {
            return null;
        }
        //建立根节点
        TreeNode root = new TreeNode(preorder[cur]);
        //寻找中序数组中当前根节点的下标
        int rootIndex = fundIndex(inorder, start, end, preorder[cur]);
        cur++;
        root.left = createTree(preorder, inorder, start, rootIndex - 1);
        root.right = createTree(preorder, inorder, rootIndex + 1, end);
        return root;
    }

    //寻找下一个分割点
    private int fundIndex(int[] inorder, int start, int end, int key)  {
        for(int i = 0; i < inorder.length; i++) {
            if(inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return createTree(preorder, inorder, 0, preorder.length - 1);
    }

    //3.最大二叉树(建树)
    public TreeNode dfs(int[] nums, int left, int right) {
        if(left > right) {
            return null;
        }
        //找到最大值建立根节点
        int val = -1; //最大值
        int valIndex = 0; //最大值下标
        for(int i = left; i <= right; i++) {
            if(nums[i] > val){
                val = nums[i];
                valIndex = i;
            }
        }
        TreeNode root = new TreeNode(val);
        root.left = dfs(nums, left, valIndex - 1);
        root.right = dfs(nums,valIndex + 1, right);
        return root;
    }

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return dfs(nums, 0, nums.length - 1);
    }

    //4.合并二叉树(dfs)
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1 == null && root2 == null) {
            return null;
        }
        if(root1 != null && root2 == null) {
            return root1;
        }
        if(root1 == null && root2 != null) {
            return root2;
        }
        //到了这里说明都不为空
        root1.val += root2.val;

        root1.left = mergeTrees(root1.left, root2.left);
        root1.right = mergeTrees(root1.right, root2.right);
        return root1;
    }

    //5.二叉搜索树中搜索(bfs)
    public TreeNode searchBST(TreeNode root, int val) {
        TreeNode cur = root;
        while(cur != null) {
            if(cur.val > val) {
                cur = cur.left;
            } else if(cur.val < val) {
                cur = cur.right;
            } else {
                return cur;
            }
        }
        return cur;
    }
//
//    //6.验证二叉搜索树(dfs)
//    private List<Integer> list = new ArrayList<>();
//    public void dfs(TreeNode root) {
//        if(root == null) {
//            return;
//        }
//        dfs(root.left);
//        list.add(root.val);
//        dfs(root.right);
//    }
//    public boolean isValidBST(TreeNode root) {
//        dfs(root);
//        //得到顺序
//        for(int i = 0; i < list.size() - 1; i++) {
//            if(list.get(i) >= list.get(i + 1)) {
//                return false;
//            }
//        }
//        return true;
//    }

    //7.合法的二叉搜索树(优化dfs)
    private int preVal = Integer.MIN_VALUE;
    private boolean flag;
    public boolean isValidBST(TreeNode root) {
        if(root == null) {
            return true;
        }
        boolean rootLeft = isValidBST(root.left);
        if(flag && root.val <= preVal) {
            return false;
        }
        flag = true;
        preVal = root.val;
        boolean rootRight = isValidBST(root.right);
        return rootLeft && rootRight;
    }

//    //8.二叉搜索树的最小绝对差
//    public void dfs(TreeNode root) {
//        if(root == null) {
//            return;
//        }
//        dfs(root.left);
//        if(prevVal == -1) {
//            prevVal = root.val;
//        } else {
//            if(Math.abs(root.val - prevVal) < minVal) {
//                minVal = root.val - prevVal;
//            }
//            prevVal = root.val;
//        }
//        dfs(root.right);
//    }
//
//    private int minVal = Integer.MAX_VALUE;
//    private int prevVal = -1;
//    public int getMinimumDifference(TreeNode root) {
//        dfs(root);
//        return minVal;
//    }

    //9.二叉搜索树中的众数(双指针-dfs)
    private void dfs(TreeNode root) {
        if(root == null) {
            return;
        }
        dfs(root.left);
        if(prev == Integer.MIN_VALUE) {
            prev = root.val;
            list.add(root.val);
        } else {
            if(root.val == prev) {
                count++;
                if(count > max) {
                    max = count;
                    list.clear();
                    list.add(root.val);
                } else if(count == max) {
                    list.add(root.val);
                }
            } else {
                count = 1;
                if(max == 1) {
                    list.add(root.val);
                }
            }
            prev = root.val;
        }
        dfs(root.right);
    }

    private List<Integer> list = new ArrayList<>();
    private int prev = Integer.MIN_VALUE;
    private int max = 1;
    private int count = 1;
    public int[] findMode(TreeNode root) {
        if(root.left == null && root.right == null) {
            list.add(root.val);
        } else {
            dfs(root);
        }
        int[] res = new int[list.size()];
        for(int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }

    //10.二叉树的最近公共祖先(自底向上)
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) {
            return null;
        }
        if(root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left != null && right != null) {
            return root;
        } else if(left == null && right != null) {
            return right;
        } else {
            return left;
        }
    }

}

class Main{
    public static void main(String[] args) {
        TreeNode t3 = new TreeNode(3);
        TreeNode t9 = new TreeNode(9);
        TreeNode t20 = new TreeNode(20);
        TreeNode t15 = new TreeNode(15);
        TreeNode t7 = new TreeNode(7);
        t3.left = t9;
        t3.right = t20;
        t20.left = t15;
        t20.right = t7;
        Solution solution = new Solution();
        int[] e = {3,9,20,15,7};
        int[] i = {9,3,15,20,7};
        solution.buildTree(e, i);
    }

}

